|
|
Predictive Parsing with Deep Pushdowns
Viktorin, Jiří ; Blatný, Petr (referee) ; Meduna, Alexandr (advisor)
This paper introduces a generalization of classical pushdown automata-deep pushdown automata. Deep pushdown automata expand a pushdown symbol in a depth defined by a rule. Deep pushdown expands a non-terminal in the deep defined in the rule and this non-terminal need not be on the top of pushdown.
|
|
|
Transducer Systems and Their Applications
Lupták, Filip ; Krčmář, Radim (referee) ; Meduna, Alexandr (advisor)
This thesis defines a new formal model „transducer system." Transducer system is composed of a number of finite transducers, which cooperate. The thesis examines expressive power of this formal model and shows that transducer system is more powerful than isolated finite transducer. This model is then used to design a parser of arithmetic expressions, which translates them to postfix notation.
|
|
| |
|
|
Parallel Versions of General Parsing
Mikita, Tibor ; Kučera, Jiří (referee) ; Meduna, Alexandr (advisor)
This thesis deals with general parsing methods. The author studies the Cocke-Younger-Kasami algorithm and comes up with a design of a parallel version. The motivation of~the author is the acceleration of parsing based on this algorithm. The result is a console application that can determine whether an input string belongs to a language generated by the input grammar or not on the basis of the designed parallel algorithm. For the programming language, C++ was chosen. To achieve parallelism the work of the algorithm was divided among several threads.
|
|
|
General Grammars: Normal Forms with Applications
Klobučníková, Dominika ; Krčmář, Radim (referee) ; Meduna, Alexandr (advisor)
This thesis deals with the topic of unrestricted grammars, normal forms, and their applications. It focuses on context-sensitive grammars as their special cases. Based on the analysis of the set, an algorithm was designed using the principles of the Cocke-Younger-Kasami algorithm to make a decision of whether an input string is a sentence of a context-sensitivegrammar. The final application, which implements this algorithm, works with context-sensitive grammars in the Penttonen normal form.
|
|
|
New Versions of Translation Automata
Baláž, Miroslav ; Klobučníková, Dominika (referee) ; Meduna, Alexandr (advisor)
This thesis does research on new version of translation automata. It takes closer look at existing pushdown transcuders and regulated grammar. Combining these two concepts together which creates new regulated pushdown transcuder as a new form of translation automata. Examine computational power of regulated grammar and tests its usage combined with transcuder and test usablity of this new defined regulated transcuder in implementation for translating input source code.
|
|
|
Grammar-Based Translation Framework
Vít, Radek ; Kolář, Dušan (referee) ; Meduna, Alexandr (advisor)
V této práci prozkoumáváme existující algoritmy pro přijímání jazyků definovaných bezkontextovými gramatikami. Na základě těchto znalostí navrhujeme nový model pro reprezentaci LR automatů a s jeho pomocí definujeme nový algoritmus LSCELR. Modifikujeme algoritmy pro přijímání jazyků k vytvoření algoritmů pro překlad založený na překladových gramatikách. Definujeme atributové překladové gramatiky jako rozšířené překladové gramatiky pro definici vztahů mezi vstupními a výstupními symboly překladu. Implementujeme překladový framework ctf založený na gramatikách, který implementuje překlad pomocí LSCELR. Definujeme jazyk pro popis atributových překladových gramatik a implementujeme překladač pro překlad této reprezentace do zdrojového kódu pro implementovaný framework.
|
|
|
Path-Controlled Grammars
Adamec, Ondřej ; Soukup, Ondřej (referee) ; Křivka, Zbyněk (advisor)
This thesis deals with path-controlled grammars, which are grammars that place restrictions on the paths in a derivation tree of a context-free grammar. The goal of this thesis is to create an algorithm for conversion between the path-controlled grammars and the state grammars, which is a di erent type of regulated grammars. Another goal is to study the generative power of path-controlled grammars based on the conversion algorithm. The conversion algorithm is implemented and tested on a number of path-controlled grammars. Also, its complexity is discussed. Finally, a parsing tool for path-controlled grammars is implemented. Complexity of this tool is analyzed as well.
|
|
|
IP Flow Filtration and Profiling
Sedlák, Michal ; Tisovčík, Peter (referee) ; Kučera, Jan (advisor)
This thesis addresses the problem of filtering and profiling IP flows, primarily data of IPFIXsystems. Within the work, a general filtering component is designed and implemented, whichaims to be sufficiently efficient and flexible for use in other projects related to IP flows. Thiscomponent is then adapted to work with data in the IPFIX protocol format and integratedinto the existing modular collector IPFIXcol2 in the form of plugins adding the support forfiltering of passing IPFIX data and their sorting into profiles.
|
|
|
Transformation of Grammars into Normal Forms
Klapuchová, Mirka ; Koutný, Jiří (referee) ; Zemek, Petr (advisor)
This thesis deals with issues of normal forms from theory of formal languages. Basic terms from this area are listed here, different types of grammars as well and especially normal forms and algorithms that transfer grammars into normal forms. Description of design and implementation of program which is used to transfer input grammar into entered normal form is included.
|
guest ::
